package com.xj.algorithm.leetcode;

import java.util.*;

/**
 * 两个数组的交集
 */
public class L349_两个数组的交集 {

    /**
     * 给定两个数组，编写一个函数来计算它们的交集。
     * <p>
     * 示例 1:
     * <p>
     * 输入: nums1 = [1,2,2,1], nums2 = [2,2]
     * 输出: [2]
     * 示例 2:
     * <p>
     * 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
     * 输出: [9,4]
     * 说明:
     * <p>
     * 输出结果中的每个元素一定是唯一的。
     * 我们可以不考虑输出结果的顺序。
     */
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 2, 1};
        int[] nums2 = new int[]{2, 2};

        int[] res=intersectionOffice(nums1,nums2);
        for (int val:res){
            System.out.print(val+",");
        }
        System.out.println();

        int[] nums3 = new int[]{4,9,5};
        int[] nums4 = new int[]{9,4,9,8,4};

        int[] res2=intersectionOffice(nums3,nums4);
        for (int val:res2){
            System.out.print(val+",");
        }
        System.out.println();
    }

    //自己的解法；hashmap找相同的结果
    public static int[] intersection(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int value : nums1) {
            if (map.get(value) == null) {
                map.put(value, value);
            }
        }

        int[] result=new int[map.size()];
        int index=0;
        for (int value : nums2) {
            Integer count = map.get(value);
            if (count != null ) {
                result[index++]=value;
                map.remove(value);
            }
        }

        int[] value=new int[index];
        for (int i=0;i<index;i++){
            value[i]=result[i];
        }
        return value;
    }

    //官方解法：内置函数retainAll
    //拷贝数组的指定范围的内容：Arrays.copyOf(output, idx);
    public static int[] intersectionOffice(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<Integer>();
        for (Integer n : nums1) set1.add(n);
        HashSet<Integer> set2 = new HashSet<Integer>();
        for (Integer n : nums2) set2.add(n);

        set1.retainAll(set2);

        int [] output = new int[set1.size()];
        int idx = 0;
        for (int s : set1) output[idx++] = s;
        return output;
    }
}
